package main

import "fmt"

/**
给你一个字符串 s 、一个字符串 t 。
返回 s 中涵盖 t 所有字符的最小子串。
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
*/
func main() {
	s := "ADOBECODEBANC"
	t := "BANC"
	fmt.Printf("minWindow(s, t): %v\n", minWindow(s, t))
}

/**
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
*/

/**
不要求按顺序覆盖
*/
func minWindow(s string, t string) string {
	if len(t) > len(s) {
		return ""
	}
	if s == t {
		return t
	}
	cnts := make(map[byte]int, 256)
	// 负数代表该字符还差多少个
	for i := 0; i < len(t); i++ {
		cnts[t[i]]--
	}
	length := 1000000
	start := 0
	debt := len(t)
	for l, r := 0, 0; r < len(s); r++ {
		// cnts[s[r]]是负数，说明还差，即s[r] 正是所需要的字符
		if cnts[s[r]] < 0 {
			// 加一个，则所需要的所有字符debt就少一个
			debt--
		}
		// 加1
		cnts[s[r]]++
		// 所需要的字符个数都有了
		if debt == 0 {
			// 左边界开始往右移动
			// 假设去掉左边界的字符，还满不满足要求，即cnts[s[l]]不能小于0
			for cnts[s[l]] > 0 {
				cnts[s[l]]--
				l++
			}
			// 左边界移动完了，看滑动窗口的长度是否缩小了
			if r-l+1 < length {
				length = r - l + 1
				// start 指向左边界
				start = l
			}
		}
	}
	if length == 1000000 {
		return ""
	}
	return s[start : start+length]
}
